import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createBinaryTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;

        C.left = F;
        C.right = G;

        E.right = H;

        return A;
    }
    /**
     * 判断是否为完全二叉树
     *      通过队列进行实现
     *      1.头元素入栈
     *      2.出栈,且无论左右子树是否为null均入栈
     *      3.递归左右子树
     *      4.当弹出为null时,停止弹出
     *      5.判断队列是否全为null,全为null则为完全二叉数,反之不是完全二叉树
     */
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) {
                break;
            }else {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        while(!queue.isEmpty()) {
            if(queue.peek() != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }
    /**
     二叉树的最近公共祖先,方法1递归遍历
     1.判断p/q是否在root上,返回root
     2.递归判断pq是否在左右两侧,存在返回root,不存在返回null
     3.递归判断pq是否在同一侧,返回遇到的结点root,不存在返回null
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return root;
        }
        if(root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) {
            return root;
        }
        if(left != null) {
            return left;
        }
        if(right != null) {
            return right;
        }
        return null;
    }
    /**
     二叉树的最近公共祖先:使用两个栈实现
     1.分别求到pq两个节点路径
     2.判断路径长度,长的路径出差值个元素
     3.分别出栈,不同,继续出栈,遇到相同节点证明为公共祖先节点
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        path(root,p,stack1);
        path(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        int size = 0;
        if(size1 > size2) {
            size = size1 - size2;
            while(size != 0) {
                stack1.pop();
                size--;
            }
        } else{
            size = size2 - size1;
            while(size != 0) {
                stack2.pop();
                size--;
            }
        }

        TreeNode tmp = null;
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            tmp = stack1.pop();
            if(tmp == stack2.pop()) {
                return tmp;
            }
        }
        return root;
    }
    /**
     1.经过路线节点全部记录
     2.判断是否为key
     3.当节点左右均为null时,证明不是路径上的节点,出栈继续走其它路径
     4.查找完毕,返回节点
     */
    public boolean path(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flagLeft = path(root.left,node,stack);
        if(flagLeft) {
            return true;
        }
        boolean flagRight = path(root.right,node,stack);
        if(flagRight) {
            return true;
        }

        stack.pop();
        return false;
    }
    /**
     从前序与中序遍历序列构造二叉树
     1.遍历前序序列
     2.遍历中序序列在中序找到前序序列对应的结点
     3.递归查找左右节点并进行连接
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
    }
    /**
     1.获取前序数组,并创建节点
     2.查找中序遍历节点位置
     3.递归查找左右
     */
    public int i;
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode((char)preorder[i]);
        //查找rootI
        int rootIndex = findRootIndex(inorder,root,inBegin,inEnd);
        i++;
        //创建二叉树
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex - 1);
        root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inEnd);

        return root;
    }
    /**
     查找中序序列中,rootIndex元素位置
     */
    public int findRootIndex(int[] inorder,TreeNode root,int inBegin,int inEnd) {
        for(int i = inBegin;i <= inEnd;i++) {
            if(inorder[i] == root.val) {
                return i;
            }
        }
        return -1;
    }
/**
 *  从前序与中序遍历序列构造二叉树
  */

    public int i2;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        i2 = postorder.length - 1;
        return buildTreeChild(inorder,postorder,0,inorder.length - 1);
    }
    private TreeNode buildTreeChild2(int[] inorder,int[] postorder,int inBegin,int inEnd) {

        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode((char)postorder[i2]);//创建头节点


        //查找后序遍历i位置节点
        int index = findIIndex(postorder[i2],inorder,inBegin,inEnd);
        i2--;
        //递归左右子树
        root.right = buildTreeChild(inorder,postorder,index + 1,inEnd);
        root.left = buildTreeChild(inorder,postorder,inBegin,index - 1);
        return root;
    }

    private int findIIndex(int key,int[] inorder,int inBegin,int inEnd) {
        for(int i = inBegin;i <= inEnd;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
